W2. Formal Language Foundations

1. Theory

1.1 Introduction to Sets

A set is one of the most fundamental concepts in mathematics and computer science. A set is a well-defined collection of distinct objects, called elements or members. When we say “well-defined,” we mean there must be a clear criterion for determining whether something belongs to the set or not—there’s no ambiguity.

Sets can be described in two main ways:

1.1.1 Explicit Enumeration

For finite sets, or when listing is practical, we can describe a set by listing all its elements between curly braces. For example:

This notation tells us that is the set containing exactly the numbers 1, 2, 4, and 8, and no other elements.

For infinite sets or very large finite sets, we sometimes use ellipsis (dots) to indicate the pattern:

However, this notation can be ambiguous—different people might interpret the pattern differently.

1.1.2 Set Comprehension (Predicate Notation)

A more reliable way to define a set is to specify the property that characterizes which elements belong to it. This is called set comprehension or defining a set by predicate:

Read as: “ is the set of all such that is a non-negative integer multiple of 3.”

The vertical bar “” means “such that.” This notation is clearer because it explicitly states the rule for membership.

1.2 Basic Set Notation and Relationships

1.2.1 Element Membership

To denote that an element belongs to a set, we use the symbol (read as “is an element of” or “is in”):

This statement is true because 2 is indeed an element of the set .

To denote that an element is NOT in a set, we use :

This is true because 4 is not in the set.

1.2.2 The Empty Set

The empty set, denoted by , is a special set that contains no elements at all. It is unique—there is exactly one empty set. The empty set is a subset of every set (we’ll explain subsets next).

1.2.3 Subsets

A set is a subset of a set , written , if and only if every element of is also an element of . In other words, doesn’t contain anything that doesn’t.

Example: because every element in is also in .

Important note: Every set is a subset of itself. Also, the empty set is a subset of every set.

1.2.4 Set Equality

Two sets are equal if and only if they have exactly the same elements. Mathematically, if and only if AND . This means:

• Every element of must be in , AND
• Every element of must be in

1.3 Sets Containing Sets

Sets can contain other sets as their elements. For example:

This set contains exactly two elements, both of which are sets themselves. Note that in this case:

• If , then (because is an element of )
• However, (because the number 1 is not a direct element of ; it’s an element of an element of )

The distinction between “” (element of) and “” (subset of) is crucial here.

1.4 Operations on Sets

Just as we can add or multiply numbers, we can perform operations on sets to create new sets. The most common operations are:

1.4.1 Union

The union of two sets and , written , is the set of all elements that belong to or (or both):

Here, “” represents the logical “or.”

Example: If and , then . Notice that even though 2 and 3 appear in both sets, we list them only once in the union.

1.4.2 Intersection

The intersection of two sets and , written , is the set of all elements that belong to both and :

Here, “” represents the logical “and.”

Example: If and , then . These are the only elements in both sets.

1.4.3 Difference

The difference of two sets and , written (sometimes ), is the set of elements in but not in :

Example: If and , then . This includes only the elements of that are not in .

1.4.4 Union of Many Sets

We can generalize the union operation to any number of sets. If we have sets (possibly infinitely many), their union is denoted:

or equivalently:

This represents the set of all elements that belong to at least one of these sets.

1.5 Power Sets

Given any set , we can form a new set consisting of all possible subsets of . This is called the power set of , denoted or sometimes .

Example: The power set of is:

This set has elements. In general, if has elements, then has exactly elements.

Why is it called ? Because the notation suggests: “the set of all subsets” can be thought of as choices (include or exclude) for each of the elements, giving total subsets.

1.6 Alphabets and Strings

An alphabet is a finite set of symbols. We typically denote alphabets with the Greek letter . For instance:

• (binary alphabet)
• (the Roman alphabet)
• (digits)

A string (also called a word or sequence) over an alphabet is a finite sequence of symbols from that alphabet. Repetitions are allowed.

Examples over :

• is a string (length 3)
• is a string (length 8)
• is a string (length 1)

The length of a string , denoted , is the number of symbols in the string.

The empty string, denoted (the Greek letter epsilon) or sometimes , is the unique string with zero symbols. By definition, .

1.7 The Set of All Strings

Given an alphabet , the set of all strings over (including the empty string) is denoted . This is an infinite set (unless is empty).

Example: For :

The strings are typically listed in order of length: first strings of length 0, then length 1, then length 2, etc.

1.8 String Concatenation

Just as we can add numbers, we can concatenate strings. If and are two strings, their concatenation, written (or sometimes ), is the string formed by writing the symbols of followed by the symbols of .

Example:

Important properties of concatenation:

1. Associativity: for all strings. The order of grouping doesn’t matter.
2. Non-commutativity: In general, . The order matters!
3. Identity element: . Concatenating with the empty string leaves the string unchanged.

We use exponential notation to represent repeated concatenation: , , etc.

1.9 Formal Languages

A language is a set of strings over an alphabet. More precisely, a language over an alphabet is any subset of :

Languages can be finite or infinite. Here are some examples:

• Over : The set of all 8-bit binary strings is a language:
• Over : The set of all strings that start with 0 is a language:
• Over : English words form a language
• Over : The set of decimal numbers is a language

The reason “language” is such a broad term is because it captures both natural languages (like English) and formal constructs (like sets of binary strings or programming language syntax).

1.10 Operations on Languages

Since a language is a set, all set operations apply to languages. Additionally, because languages consist of strings, we can use string operations to define new languages.

1.10.1 Set Operations on Languages

The fundamental operations are:

• Union: — strings in either language
• Intersection: — strings in both languages
• Difference: — strings in but not
• Complement: — all strings over not in

1.10.2 Concatenation of Languages

If and are languages over the same alphabet , their concatenation is:

This is the set of all strings formed by taking a string from and concatenating it with a string from .

Example: If and , then:

Note that concatenation of languages is not commutative: generally .

Also, there’s an interesting property: if , then doesn’t necessarily hold in both directions.

1.10.3 Power of a Language

The power of a language is obtained by concatenating the language with itself. For a positive integer :

We define — a language containing only the empty string.

Example: If , then:

When working with an alphabet , the power represents all strings of length exactly :

1.10.4 The Kleene Star (Kleene Closure)

The Kleene star is one of the most important operations in formal language theory. For a language , the Kleene star (or Kleene closure) of , written , is defined as:

This definition can seem complex, so let’s break it down:

• We take zero or more strings from
• We concatenate them together
• is the set of ALL possible results of such concatenations
• The “zero or more” part means that the empty string is always in (when we take zero strings and concatenate them, we get )

Example: If , then:

This is all strings consisting of the symbol repeated any number of times (including zero times, giving ).

Another example: If , then:

The Kleene star is called a “closure” because applying it to any set gives you a closed set under the concatenation operation—if you take any two strings from and concatenate them, you get another string in .

1.10.5 The Kleene Plus

A related operation is the Kleene plus, written , which is like the Kleene star but excludes the empty string:

This represents one or more concatenations of strings from (but at least one is required).

Example: If , then:

Note the difference: includes , but does not.

1.11 Notation Summary for Special Cases

For an alphabet and a string :

• (by convention, any string to the power 0 is the empty string)
• (concatenating with itself times)
• (all strings of length exactly over )
• (all strings of any length over )
• (all non-empty strings over )

---

2. Definitions

• Alphabet: A finite set of symbols, typically denoted . Examples include , , or any finite collection of distinct symbols.
• String (also word or sequence): A finite sequence of symbols from an alphabet, where repetitions are allowed. The length of a string , denoted , is the number of symbols it contains.
• Empty String: The unique string containing zero symbols, denoted (epsilon). By definition, .
• Set: A well-defined collection of distinct objects called elements. Sets are determined by the property of their elements: for any object, it either is or is not an element of the set (no ambiguity).
• Element: An object belonging to a set. We write to denote that is an element of set , and to denote that it is not.
• Subset: Set is a subset of set , written , if every element of is also an element of . Every set is a subset of itself, and the empty set is a subset of every set.
• Empty Set: The unique set containing no elements, denoted . The empty set is a subset of every set.
• Set Equality: Two sets and are equal (written ) if and only if they have exactly the same elements, i.e., and .
• Union of Sets: The union of sets and , denoted , is the set of all elements that belong to or (or both): .
• Intersection of Sets: The intersection of sets and , denoted , is the set of all elements that belong to both and : .
• Set Difference: The difference of sets and , denoted or , is the set of elements in but not in : .
• Power Set: The power set of a set , denoted or , is the set of all subsets of , including the empty set and itself. If has elements, then has elements.
• Set Comprehension: A method of defining a set by specifying a property that characterizes its elements: means “ is the set of all such that property is true.”
• Language: A language over an alphabet is a set of strings over , i.e., any subset of . Languages can be finite or infinite.
• : The set of all strings over alphabet , including the empty string. This is the union of all strings of every possible length: .
• String Concatenation: The operation of joining two strings end-to-end. If and are strings, their concatenation (or ) is the string formed by writing the symbols of followed by the symbols of . Concatenation is associative but not commutative.
• Concatenation of Languages: For languages and , their concatenation is , the set of all strings formed by concatenating a string from with a string from .
• Power of a Language: The -th power of a language , denoted , is the concatenation of with itself times. By convention, .
• Kleene Star (Kleene Closure): For a language , the Kleene star is the set of all strings obtained by concatenating zero or more strings from : . This always includes the empty string .
• Kleene Plus: For a language , the Kleene plus is the set of all strings obtained by concatenating one or more strings from : . This excludes the empty string.
• Complement of a Language: For a language over alphabet , the complement (or ) is the set of all strings over that are not in : .
• Cardinality: The cardinality of a finite set , denoted , is the number of elements in . For infinite sets, cardinality refers to the “size” of the set in a more abstract sense.
• Free Monoid: The set with string concatenation as the operation. A monoid is a set with an associative binary operation and an identity element (here, is the identity). The term “free” indicates there are no additional constraints on how strings can be combined.

---

3. Formulas

• Set Union:
• Set Intersection:
• Set Difference:
• Union of Multiple Sets:
• Power Set Cardinality: If , then
• String Length: denotes the number of symbols in string ;
• String Concatenation: If and are strings, then $xy = $ the string formed by writing symbols of followed by symbols of
• Concatenation Associativity: for all strings
• Concatenation Identity: for any string
• Power of a String: for ;
• Language Concatenation:
• Power of a Language: ;
• Kleene Star:
• Kleene Plus:
• Strings of Exact Length:
• All Strings over Alphabet:
• All Non-empty Strings:
• Language Complement:

---

4. Practice

4.1. Determining Sets from Descriptions (Lab 2, Task 1.1)

Determine the set .

Click to see the solution

Key Concept: This set consists of singleton sets (sets containing one element). We need to identify which singleton sets are included based on the condition that must be a non-negative integer at most 4.

1. Identify the non-negative integers satisfying the condition: We need where , so .
2. Form singleton sets for each value: For each such , we create a set containing just that element:
   • For :
   • For :
   • For :
   • For :
   • For :
3. Collect all these singleton sets into :

Answer:

4.2. Determining Sets from Descriptions (Lab 2, Task 1.2)

Determine the set .

Click to see the solution

Key Concept: This set consists of all non-negative integer linear combinations of 3 and 5. We need to determine which non-negative integers can be expressed as .

1. List some elements: Let’s systematically find values by trying different values of and :
   • :
   • :
   • :
   • :
   • :
   • :
   • :
   • And so on…
2. Identify which integers CAN be represented: It can be shown that every non-negative integer except 1, 2, 4, and 7 can be represented as . This is related to the Frobenius coin problem: with denominations of 3 and 5, the largest amount that cannot be made is .
3. Write the set explicitly:

Answer: (all non-negative integers except 1, 2, 4, and 7)

4.3. Set Equality (Lab 2, Task 1.3)

Are the sets and equal?

Click to see the solution

Key Concept: Sets are determined solely by their elements, not by the order in which elements are listed.

1. Identify the elements of the first set: contains the elements 0 and 1.
2. Identify the elements of the second set: contains the elements 1 and 0.
3. Compare: Both sets contain exactly the same elements: 0 and 1.
4. Verify set equality: Two sets are equal if and only if they have exactly the same elements. Since both and contain the same elements (0 and 1), they are equal.

Answer: Yes, . Order does not matter in sets.

4.4. Set Equality and Duplicates (Lab 2, Task 1.4)

Are the sets and equal?

Click to see the solution

Key Concept: In set notation, duplicate elements are listed only once. A set is determined by which distinct elements it contains.

1. Identify the distinct elements in the first set: contains 0 (repeated), 1 (repeated), and 2 (listed once). The distinct elements are: .
2. Identify the distinct elements in the second set: contains 1 (repeated), 0, and 2 (repeated). The distinct elements are: .
3. Compare: Both sets have exactly the same distinct elements: 0, 1, and 2.
4. Conclusion: Since both representations describe the same set, they are equal.

Answer: Yes, .

4.5. Power Set Construction (Lab 2, Task 2.1)

Construct the power set of .

Click to see the solution

Key Concept: The power set consists of ALL subsets, including the empty set and the set itself.

1. List all possible subsets of :
   • The subset containing no elements:
   • Subsets containing one element: ,
   • Subsets containing two elements:
2. Verify completeness: For each element, we have a choice to include it or exclude it:
   • Exclude and :
   • Include only :
   • Include only :
   • Include both and :
3. Count: We have 2 elements, so we expect subsets. We listed 4, which is correct.

Answer:

4.6. Power Set Construction (Lab 2, Task 2.2)

Construct the power set of .

Click to see the solution

Key Concept: First, simplify the set by computing the union, then find all subsets.

1. Compute the union: .
2. Find all subsets of :
   • Zero elements:
   • One element: , ,
   • Two elements: , ,
   • Three elements:
3. Verify count: With 3 elements, we expect subsets. We have 8, which is correct.

Answer:

4.7. Power Set Construction (Lab 2, Task 2.3)

Construct the power set of .

Click to see the solution

Key Concept: A singleton set (set with one element) has a power set with subsets.

1. Identify all subsets of :
   • The empty set:
   • The set containing :

Answer:

4.8. Set Operations and Power Sets (Lab 2, Task 2.4)

Construct the power set of .

Click to see the solution

Key Concept: First find the intersection, then construct its power set.

1. Compute the intersection: We need elements that are in BOTH sets.
   • Is 0 in both? but . No.
   • Is 1 in both? Yes.
   • Is 2 in both? No.
   • Is 3 in both? Yes.
   • Is 4 in both? No.
   • Is 5 in both? No.
   • Is in both? No.
   Therefore:
2. Find the power set of :

Answer:

4.9. Set Operations and Power Sets (Lab 2, Task 2.5)

Construct the power set of .

Click to see the solution

Key Concept: First find the set difference, then construct its power set.

1. Compute the set difference: We need elements in the first set but NOT in the second.
   • Is 0 in the first set but not the second? and . Yes.
   • Is 1 in the first but not the second? but . No.
   • Is 2 in the first but not the second? Yes.
   • Is 3 in the first but not the second? No.
   Therefore:
2. Find the power set of :

Answer:

4.10. Power Set of Empty Set (Lab 2, Task 2.6)

Construct the power set of .

Click to see the solution

Key Concept: The power set of the empty set contains the empty set as its only element.

1. Find all subsets of : The only subset of the empty set is the empty set itself.
2. Verify count: With 0 elements, we expect subset. We have 1, which is correct.

Answer:

4.11. Formal Language Basics (Lab 2, Task 2.7)

Determine for any alphabet .

Click to see the solution

Key Concept: represents all strings of length exactly over the alphabet . So contains all strings of length 0.

1. Find all strings of length 0: There is exactly one string of length 0: the empty string .
2. Therefore:

Answer: for any alphabet .

4.12. All Strings of Exact Length (Lab 2, Task 2.8)

Determine for .

Click to see the solution

Key Concept: consists of all strings of length exactly 4 over the binary alphabet.

1. Count the number of strings: Each position can be filled with either 0 or 1, and there are 4 positions. This gives strings.
2. List all strings of length 4 over :
   • Starting with 00:
   • Starting with 01:
   • Starting with 10:
   • Starting with 11:

Answer:

4.13. Power Set of an Alphabet (Lab 2, Task 2.9)

Determine for .

Click to see the solution

Key Concept: is the power set of the alphabet itself, containing all subsets of .

1. List all subsets of :
   • The empty subset:
   • Subsets with one element: ,
   • The subset with both elements:
2. Verify count: With 2 elements, we expect subsets. We have 4, which is correct.

Answer:

4.14. Power Set of All Strings (Lab 2, Task 2.10)

Determine for .

Click to see the solution

Key Concept: is an infinite set of all strings over . Its power set is the set of all subsets of .

1. Understand the structure: is an infinite set containing all possible finite strings.
2. Determine : This is the power set of an infinite set, so it is also infinite (in fact, it has a higher level of infinity than ).
3. Examples of elements in :
   • (the empty language)
   • (language containing only empty string)
   • (language containing only two single-symbol strings)
   • (the language of all strings)
   • The set of all strings starting with 0
   • The set of all strings with even length
   • Any other subset of

Answer: is the set of all subsets of (all possible languages over ). It is an uncountably infinite set with elements.

4.15. Find Alphabets for Languages (Lab 2, Task 3.1)

Find a possible alphabet for the language .

Click to see the solution

Key Concept: An alphabet must contain all distinct symbols that appear in the strings of the language.

1. List all strings in the language:
2. Identify all distinct characters that appear:
   • In “oh”: characters and
   • In “ouch”: characters , , ,
   • In “ugh”: characters , ,
3. Collect all distinct characters:
4. Verify: Every string in the language consists only of characters from this set.

Answer: A possible alphabet is (or any superset of this).

4.16. Find Alphabets for Languages (Lab 2, Task 3.2)

Find a possible alphabet for the language .

Click to see the solution

Key Concept: The alphabet must include all characters appearing in any string of the language.

1. Identify all distinct characters:

   • In “apple”:
   • In “pear”:
   • In “4711”:

2. Collect all distinct characters:

   Removing duplicates:

Answer: A possible alphabet is (or any superset containing at least these characters).

4.17. Find Alphabets for Languages (Lab 2, Task 3.3)

Find a possible alphabet for the language of all binary strings.

Click to see the solution

Key Concept: Binary strings use only two symbols: 0 and 1.

1. Identify the symbols needed: Binary strings consist of sequences of 0’s and 1’s.

Answer:

4.18. Kleene Star over Different Alphabets (Lab 2, Task 3.4)

Determine what produces for .

Click to see the solution

Key Concept: is the set of all strings (of any length) over .

1. Description:
2. Interpretation: This is the set of all finite binary strings, including the empty string.

Answer: (all binary strings of any length)

4.19. Kleene Star over Different Alphabets (Lab 2, Task 3.5)

Determine what produces for .

Click to see the solution

Key Concept: When the alphabet contains a single symbol, contains all repetitions of that symbol.

1. List the contents:
   • Length 0:
   • Length 1:
   • Length 2:
   • Length 3:
   • And so on…
2. Expression:

Answer:

4.20. Kleene Star over Empty Alphabet (Lab 2, Task 3.6)

Determine what produces for (the empty alphabet).

Click to see the solution

Key Concept: If we have no symbols available, we can’t form any non-empty strings. We can only form the empty string.

1. Analyze: Without any symbols in the alphabet, the only string we can form is the empty string (which uses zero symbols).

Answer: (only the empty string)

4.21. Determining the Alphabet (Lab 2, Task 4.1)

For the language , determine the alphabet .

Click to see the solution

Key Concept: We identify the symbols that appear in the strings of the language.

1. Observe the strings: The language contains all strings using symbols 0 and 1.
2. Identify the alphabet: The only symbols appearing are 0 and 1.

Answer:

4.22. Determining the Alphabet (Lab 2, Task 4.2)

For the language , determine the alphabet .

Click to see the solution

Key Concept: We identify which symbols appear in the language.

1. Observe: All strings consist only of the symbol repeated.

Answer:

4.23. Language Complement (Lab 2, Task 4.3)

Assuming , construct the complement for .

Click to see the solution

Key Concept: The complement of a language is the set of all strings over that are NOT in .

1. Define the complement:
2. Description: consists of all binary strings except 010, 101, and 11. This includes:
   • (the empty string)
   • All single-symbol strings:
   • All two-symbol strings except nothing (since we excluded three-symbol strings, not two-symbol):
   • All three-symbol strings except 010 and 101:
   • All four-symbol strings and beyond
3. Explicit representation:

Answer: (all binary strings except 010, 101, and 11)

4.24. Language Complement (Lab 2, Task 4.4)

Assuming , construct the complement for .

Click to see the solution

Key Concept: We need to find the complement of a language that is “all strings except 110”.

1. Understand the original language: $L = ^* {110} = $ all binary strings except the string 110.

2. Find the complement:

   By set theory,

3. Verify: The strings in are partitioned into two groups:

   • Those in (all strings except 110)
   • Those not in (which is only 110)

   So the complement of is exactly the set of strings not in , which is .

Answer:

4.25. Power Set Difference (Lab 2, Task 4.5)

Determine the set .

Click to see the solution

Key Concept: Find the power sets first, then compute their difference.

1. Compute :
2. Compute :
3. Compute the difference: We need elements in the first set but not in the second.
   • Is in both? Yes. Not in difference.
   • Is in both? Yes. Not in difference.
   • Is in the first? Yes. Is in the second? No. Include it.
   • Is in the first? Yes. Is in the second? No. Include it.
4. Result:

Answer:

4.26. Set Comprehension (Lab 2, Task 4.6)

Determine the set where is the set of all non-negative integers.

Click to see the solution

Key Concept: This notation describes values of where there exists some such that .

1. Interpret the condition: We need to find all non-negative integers such that there exists a non-negative integer with and .
2. Find all possible values: Since , we have .
   • If :
   • If :
   • If :
   • …
   • If :
3. Result:

Answer:

4.27. Language Concatenation (Lab 2, Task 5.1)

Let be a language over . Find and .

Click to see the solution

Key Concept: consists of the empty string and all strings of consecutive ’s (with no ’s). We need to find its complement and its Kleene star.

(a) Finding (the complement):

1. Understand : — strings consisting of zero or more ’s only.
2. Define the complement: — all strings over that are NOT in .
3. Characterize strings in : These are strings containing at least one (since the only strings without are in ).
4. Express as a set:

(b) Finding (the Kleene star):

1. Recall the definition:

2. Analyze: We concatenate zero or more strings from . Each string in is of the form for some .

3. Compute the concatenation: If we take strings from and concatenate them:

4. Determine the result: Since for all , the sum can be any non-negative integer. Therefore:

   Since already contains all strings of the form for , we have .

Answer:

4.28. Language Concatenation (Example) (Lab 2, Task 5.2)

Let and over . Find .

Click to see the solution

Key Concept: Language concatenation creates all possible concatenations of a string from with a string from .

1. Identify the elements:
   • (3 elements)
   • (2 elements)
2. Form all concatenations: For each element in and each element in , form :
3. Collect unique strings:

Answer:

4.29. Language Concatenation (Example) (Lab 2, Task 5.3)

Let and over . Find .

Click to see the solution

Key Concept: First, expand the exponential notation. means repetitions of , and .

1. Expand the sets:
   • (since )
2. Form all concatenations:
3. Result:

Answer:

4.30. Language Power (Lab 2, Task 5.4)

Let . Find .

Click to see the solution

Key Concept: consists of all concatenations of two strings from .

1. Identify the elements of :
2. Form all concatenations of pairs:
3. Check for duplicates: All concatenations are unique.

Answer:

4.31. Describing Languages in English (Lab 2, Task 5.5)

Describe the language over in plain English.

Click to see the solution

Key Concept: is the Kleene star of the two-element set, meaning all possible concatenations of ’s and ’s.

1. Understand the notation: is the set of all strings that can be formed using the symbols and .
2. Content:
   • The empty string
   • All single-symbol strings:
   • All two-symbol strings:
   • All three-symbol strings:
   • And so on…

Answer: The language of all finite strings over the alphabet , including the empty string. Equivalently: all possible sequences of ’s and ’s of any length.

4.32. Describing Languages in English (Lab 2, Task 5.6)

Describe the language over in plain English.

Click to see the solution

Key Concept: This is the union of two Kleene stars: strings of ’s and strings of ’s.

1. Analyze : This is the set of all strings consisting of zero or more ’s:
2. Analyze : This is the set of all strings consisting of zero or more ’s:
3. Union:

Answer: The language consisting of all strings that are either all ’s or all ’s (including the empty string). In other words: strings containing only ’s, or only ’s, but not a mix of both.

4.33. Describing Languages in English (Lab 2, Task 5.7)

Describe the language over in plain English.

Click to see the solution

Key Concept: The intersection contains only elements that are in BOTH sets.

1. Identify : All strings of ’s (including )
2. Identify : All strings of ’s (including )
3. Find the intersection: What strings are in BOTH sets? A string can be in only if it contains no ’s. A string can be in only if it contains no ’s. The only string that satisfies both conditions is the empty string .
4. Result:

Answer: The language containing only the empty string:

4.34. Describing Languages in English (Lab 2, Task 5.8)

Describe the language over in plain English.

Click to see the solution

Key Concept: We’re taking the difference of two languages related to even repetitions of .

1. Understand : Concatenations of the string “aa”: This is all strings of ’s with even length.
2. Understand : Concatenations of the string “aaaa”: This is all strings of ’s with length divisible by 4.
3. Compute the difference: consists of strings in the first but not the second.
   • Strings in : even-length strings of ’s
   • Strings in : 4-divisible-length strings of ’s
   • Difference: even-length but not 4-divisible
4. Characterize: These are strings of ’s with length (i.e., length )

Answer: Strings of ’s whose length is even but not divisible by 4. Examples:

4.35. String Expansion (Lab 2, Task 5.9)

Write out in full: .

Click to see the solution

Key Concept: Exponential notation represents repetition of strings.

1. : The symbol 0 repeated 5 times:
2. : The symbol 0 repeated 3 times, followed by the symbol 1 repeated 3 times:
3. : The string “010” repeated 2 times:
4. : The string “01” repeated 3 times, followed by the digit 0 (i.e., ):
5. : Any string to the power 0 is the empty string:

Answer:

• (empty string)

4.36. Complex Language Operations (Lab 2, Task 6.1)

Perform the following operations on languages over :

Find: 1. and 2. , , , ,

Click to see the solution

Key Concept: These are complex operations on languages. Let’s first clarify what each language is.

1. Clarify the languages:

   • — strings of identical repeated symbols (all 0’s or all 1’s, length ≥ 1)

     More formally:

   • — all binary strings

   • — all strings of length 1:

   • — all strings of length 2:

   • — all non-empty strings:

(Part 1a: )

• (every string in is also in since consists of binary strings)
• Therefore:

(Part 1b: )

• (single-character strings)
• (two-character strings)

(Part 2a: )

• , so

(Part 2b: )

• Strings of length 1 in : only and
• Therefore:

(Part 2c: )

• Strings of length 2 in : only and (not mixed strings like or )
• Therefore:

(Part 2d: )

• contains no empty string (all elements have length ≥ 1)
• is all non-empty strings
• Therefore:

(Part 2e: )

• (length 1)
• (length 2)
• No string can have both length 1 and length 2
• Therefore:

Answer: 1. and 2. - - - - -

4.37. Language Set Difference (Lab 2, Task 6.2)

For the same languages from Exercise 5, find: 3. , , , ,

Click to see the solution

(Part 3a: )

• , so there are no elements in that are not in
• Therefore:

(Part 3b: )

• Remove strings of length 1 from :

(Part 3c: )

• (length 1)
• (length 2)
• No string in is in (different lengths)
• Therefore:

(Part 3d: )

• (all strings of length 2)
• (all non-empty strings)
• All strings in have length ≥ 1, so all are in
• Therefore:

(Part 3e: )

• (all non-empty strings)
• (all length-2 strings)
• Remove length-2 strings from : get all non-empty strings except those of length 2
• Therefore:

Answer: 3. - - - - - (all non-empty strings except those of length 2)

4.38. Language Complements (Lab 2, Task 6.3)

For the same languages from Exercise 5, find: 4. , , ,

Click to see the solution

(Part 4a: )

• (repetitions of a single symbol)
• (all strings except pure repetitions)
• This includes: , and all strings containing both 0’s and 1’s or with mixed patterns
• More specifically:

(Part 4b: )

• (all binary strings)
• (complement of the universal language is empty)

(Part 4c: )

• (strings of length 1)
• (all strings except 0 and 1)
• This is: (empty string and strings of length ≠ 1)

(Part 4d: )

• From previous exercise: (non-empty strings except length-2)
• The complement contains: strings of length 2, or the empty string
• Therefore:

Answer: 4. - (empty string or mixed strings) - - (empty string and non-length-1 strings) - (empty string and all length-2 strings)

4.39. Language Concatenation (Lab 2, Task 6.4)

For the same languages from Exercise 5, find: 5. , ,

Click to see the solution

(Part 5a: )

• (all binary strings)

1. Analyze: For each string in (a repetition of one symbol) and concatenate with any string in (any binary string)
2. Examples:
   • Take and :
   • Take and :
3. Characterization: Can we get any binary string from ?
   • Take any binary string . We want to show
   • If , we need and with . This is impossible since contains no empty string
   • If starts with 0, write where is any string. Take and
   • If starts with 1, write . Take and
4. Result:

(Part 5b: )

• (single symbols)
• (two-symbol strings)

1. Form all concatenations:
2. Result: (all 3-bit strings)

(Part 5c: )

• (two-symbol strings)
• (single symbols)

1. Form all concatenations:
2. Result: (all 3-bit strings)

Answer: 5. - (all non-empty strings) - -

4.40. Language Kleene Star and Plus (Lab 2, Task 6.5)

For the same languages from Exercise 5, find: 6. , ,

Click to see the solution

(Part 6a: )

• (all binary strings)
• $L_2^* = $ all concatenations of zero or more strings from

1. Analyze: Any string we concatenate from is already a binary string. Concatenating binary strings gives binary strings.
2. Verify inclusion both ways:
   • Is every string in a binary string? Yes, because contains only binary strings, so any concatenation is binary
   • Is every binary string in ? Any binary string can be written as (a single concatenation from ), so yes
3. Result:

(Part 6b: )

• (single-character strings)
• $L_3^* = $ all concatenations of zero or more strings from

1. Understand: We can concatenate any number of single symbols (0’s and 1’s) to form any binary string
2. Verify:
   • Any concatenation of symbols from gives a binary string
   • Any binary string is a concatenation of single 0’s and 1’s
   • We can concatenate zero symbols to get
3. Result: (all binary strings)

(Part 6c: )

• (all 2-character strings)
• $L_4^* = $ all concatenations of zero or more 2-character strings

1. Analyze: Each string in is formed by concatenating pairs of characters
   • Zero concatenations:
   • One concatenation: any 2-character string from
   • Two concatenations: any 4-character string made of two 2-character parts
   • Three concatenations: any 6-character string
   • Generally: strings of even length
2. Key observation: If we concatenate strings each of length 2, we get a string of length
3. Possible lengths: (empty), , , , etc. — all even lengths
4. Result: (all binary strings of even length, including the empty string)

Answer: 6. - (all binary strings) - (all binary strings) - (binary strings with even length, including )

4.41. Alphabet Determination from Language (Tutorial 2, Example 1)

For the language , determine the minimal alphabet .

Click to see the solution

Key Concept: The minimal alphabet must contain all symbols used in the language, but no unnecessary symbols.

1. Understand the language: The language consists of all strings that start with the digit 0. This could be , etc.
2. Identify used symbols: Any string starting with 0 must contain the symbol 0. The strings after the initial 0 can contain any symbols from the alphabet.
3. Minimal alphabet: To have at least one non-zero string in the language (besides just “0”), we need at least one more symbol. The minimal choice is to add just one more symbol, say 1.
4. Verification: With , the language makes sense and matches our description.

Answer: The minimal alphabet is or any two-symbol alphabet where one symbol is 0.

4.42. Concatenation Identity Property (Tutorial 2, Example 2)

Verify that concatenation is associative and identify the identity element.

Click to see the solution

Key Concept: We need to show and find an element such that .

Associativity:

1. Define: For strings , , and
2. Compute :
   • First:
   • Then:
3. Compute :
   • First:
   • Then:
4. Conclusion: Both give the same result, so .

Identity Element:

1. Test (empty string):
   • (no symbols before )
   • (no symbols after )
2. Conclusion: is the identity element for string concatenation.

Answer: Concatenation is associative: . The identity element is (empty string): for all strings .